package com.qjc.demo.train.gragh.adjacencylist;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * @ClassName: Gragh2
 * @Description: 邻接表实现图
 * @Author: qjc
 * @Date: 2022/5/2 10:41 PM
 */
public class Gragh2 {

    Map<String, Vertex> vertexMap = new HashMap<>();// 存储所有的结点

    /**
     * 插入结点
     *
     * @param name 结点名称
     */
    public void insertVertx(String name) {
        Vertex vertex = new Vertex(name, null);// 定义结点
        vertexMap.put(name, vertex);
    }

    /**
     * 插入边
     *
     * @param start  起点名称
     * @param end    终点名称
     * @param weight 边的权重
     */
    public void insertEdge(String start, String end, int weight) {
        Vertex startVertex = vertexMap.get(start);// 获取起点
        if (startVertex == null) {
//            return;// 如果起点不存在，则不让其插入边
            // 也可以新建结点
            startVertex = new Vertex(start, null);
            vertexMap.put(start, startVertex);
        }
        // 新建边
        Edge newEdge = new Edge(end, weight, null);
        if (startVertex.next == null) {
            startVertex.next = newEdge;
        } else {
            Edge endEdge = startVertex.next;
            while (endEdge.next != null) {
                endEdge = endEdge.next;
            }
            endEdge.next = newEdge;
        }
    }

    // 打印邻接表
    public void print() {
        Set<Map.Entry<String, Vertex>> entrySet = vertexMap.entrySet();
        Iterator<Map.Entry<String, Vertex>> iterator = entrySet.iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Vertex> entry = iterator.next();
            Vertex vertex = entry.getValue();
            Edge edge = vertex.next;
            while (edge != null) {
                System.out.println(vertex.name + "指向" + edge.name + "权重是" + edge.weight);
                edge = edge.next;
            }
        }
    }

    public static void main(String[] args) {
        Gragh2 gragh2 = new Gragh2();
        gragh2.insertVertx("A");
        gragh2.insertVertx("B");
        gragh2.insertVertx("C");
        gragh2.insertVertx("D");
        gragh2.insertVertx("E");
        gragh2.insertVertx("F");

        gragh2.insertEdge("A", "B", 4);
        gragh2.insertEdge("A", "D", 5);
        gragh2.insertEdge("C", "A", 1);
        gragh2.insertEdge("D", "E", 3);
        gragh2.insertEdge("D", "F", 4);
        gragh2.insertEdge("E", "B", 2);
        gragh2.insertEdge("F", "C", 2);

        gragh2.print();
    }

}
